In a few years time, (self) localization of mobile devices or terminal devices will be among the most important basics for modern user-friendly applications. With a continuously increasing spreading of convenient mobile devices (such as, for example, PDAs, Smartphones) in connection with an extensive availability of digital or analog transmission technologies (such as, for example, WLAN, UMTS, GSM), the market for applications which provide the user with location-relevant information in any situation is growing as well. Today's applications are mainly based on the satellite navigation system NAVSTAR-GPS. However, in intra-urban regions with high buildings, tunnels and bridges, and within buildings (such as, for example, airports, stations, trade fair centers), it is frequently not able to provide a position or only a very imprecise position, since the satellite signals are attenuated or influenced too strongly. It is especially these locations which exhibit a high visitor frequency. What is useful is an alternative, cheap and reliable localization technology taking this scenario into account.
The WLAN standard in accordance with IEEE 802.11 (a,b,g) has become established for the wireless network connection of portable devices. It is under continuous development, with regard to both data rate and range. The established standards, and the 802.11n standard worked on at present, allow broad-band data transmission at high data rates and exhibit a high degree of integration which allows using cheap hardware. Wireless interfaces, such as, for example, WLAN mentioned, are most frequently integrated in current PDAs and Smartphones. Additionally, Bluetooth and, in the future, maybe WIMAX are employed frequently.
In the case of WLAN, commercial public WLAN access points (hot spots) are meanwhile available in many locations of high visitor frequency. In addition, the rapidly increasing spreading of broad-band Internet access (exemplarily using DSL) has supported the spreading of WLAN as a cheap home-networking technology in the private sector as well. Several studies have revealed that intra-urban regions today are covered by WLAN almost exhaustively in many communities, or even over-covered. Particularly locations of everyday life and of interest for tourists are well-equipped in this regard.
At present, it seems to be practical to use WLAN as a basic technology for localization. Other technologies to which the inventive concept discussed below may also be applied will surely be employed one day. Localization in WLAN networks may principally be performed by evaluating the base stations received (hot spot) or access points), wherein exemplarily the respective signal strength received on the terminal device is evaluated. However, WLAN signals are shielded strongly by buildings and other obstacles, wherein in particular in regions of comprehensive WLAN provision, there are typically no ideal free-field conditions since they are located in urban areas. The consequence is that it is not possible to directly deduce the distance to a base station or another communication partner using the signal strength or field strength measured. A public environment or a dynamically changing environment (such as, for example, a warehouse) is principally subject to non-influenceable changes (build up/disassembly/exchange of access points, temporally limited activity of the access points, etc.)
In WLAN-based localization systems, so-called received signal strength (RSS) fingerprinting is frequently used as a basic method. This method is based on the assumption that signal strengths received or receivable at a current location from radio signals of several radio stations unambiguously characterize the current location or the current position. If there is a reference database which contains, for a number of reference locations or reference positions, transmitter identifications of radio stations received or receivable there at reference points in time, and the signal strengths of the corresponding radio signals, the current position can be deduced from a set of current measuring values (transmitter identifications and signal strength values belonging thereto) by matching currently measured measuring values and the reference values of the database. This matching evaluates for every reference point how similar its measuring or reference values recorded before are to the current measuring values of the current position. The most similar reference point(s) is/are then used as a basis for an estimated value for the current whereabouts of the mobile terminal device.
The signal strength of a radio transmitter receivable at a reference position at a reference measuring time is determined experimentally for a reference database by a reference measurement. The result is a database which contains a list of radio transmitters (access points) including the respective associated receive field strength and quality for every reference position where a reference measurement was performed before. This list may also be referred to as reference packet. With a WLAN implementation, such a reference database may exemplarily contain the following parameters:
RIDMACRSSIPGSXYZMAPNRCREATED100.0D.54.9E.17.8146530100579515627150012.03.07 12:42100.0D.54.9E.1A.BA6726090579515627150012.03.07 12:42100.0D.54.9E.1D.647200288579515627150012.03.07 12:42100.0E.6A.D3.B9.8B59531100579515627150012.03.07 12:42100.0F.A3.10.07.6C4646496579515627150012.03.07 12:42100.0F.A3.10.07.FB7448894579515627150012.03.07 12:42100.0F.A3.10.09.SF7237597579515627150012.03.07 12:42200.0D.54.9E.17.81541381001439915451150012.03.07 12:43200.0D.54.9E.18.1D76560111439915451150012.03.07 12:43200.0D.54.9E.1A.BA62318941439915451150012.03.07 12:43200.0D.54.9E.1D.6471348961439915451150012.03.07 12:43200.0E.6A.D3.B9.8B453931001439915451150012.03.07 12:43200.0F.A3.10.07.6C66853961439915451150012.03.07 12:43200.0F.A3.10.07.FB722511001439915451150012.03.07 12:43200.0F.A3.10.09.5F70990901439915451150012.03.07 12:43300.0D.54.9E.17.81582911002458315627150012.03.07 12:43300.0D.54.9E.18.1D78610682458315627150012.03.07 12:43300.0D.54.9E.1A.BA62153982458315627150012.03.07 12:43300.0D.54.9E.1D.6464187902458315627150012.03.07 12:43300.0E.6A.D3.B9.8B328511002458315627150012.03.07 12:43300.0F.A3.10.07.6C69006962458315627150012.03.07 12:43300.0F.A3.10.07.FB 71749922458315627150012.03.07 12:43300.0F.A3.10.09.5F 71482832458315627150012.03.07 12:43300.0F.A3.10.09.8071000402458315627150012.03.07 12:43
The table contains the following information:                reference position identification (RID)        MAC addresses of the stations received        receive field strengths of the radio transmitters (RSSI (Received Signal Strength Indicator); 46560 means −46.560 dBm)        reference position in Cartesian metric coordinates (x, y, z; 24583 means 245.83 m), and        time of taking the measuring value.        
The column PGS (“Percentage Seen”) indicates how frequently this station was seen on a percentage basis when taking the measuring values (i.e. PGS=90 means that the station was measured on average in 9 out of 10 measurements).
In the table illustrated above, all the information associated with a reference position identification (RID) correspond to a reference measurement packet. This means that the above exemplary table includes three reference measurement packets corresponding to three different geographical reference positions.
When localizing, currently received radio transmitters including their respective associated received field strengths (measurement packet) are compared to reference packets from the reference database in a matching phase. Reference packets of smaller a distance to the current measurement packet, i.e. many common radio transmitters and few differing received field strengths, fit the current measurement packet well. The reference positions belonging to the well-fitting reference packets are very probable and are considered in a position calculating phase. An estimated value for the current position exemplarily results from a reference position associated with a reference packet most similar to the current measurement packet or from an interpolation of several reference positions associated with similar reference packets.
A conventional distance formula frequently used in the matching phase:
                    acc        =                              ∑                          n              =              1                        Neq                    ⁢                                          ⁢                      Δ            ⁢                                                  ⁢                          RSSI              n                                                          (        1        )            assumes that all radio transmitters can be received everywhere. In equation (1), acc stands for the distance between the current measurement packet and the reference packet, and Neq for a number of radio transmitters of which transmitter identifications recorded before at the reference positions are identical to transmitter identifications provided at the current position. Differences of RSSI values of radio transmitters of which transmitter identifications recorded before at the reference position are identical to transmitter identifications provided at the current position, are referred to as ΔRSSIn (n=1, . . . , Neq). However, this conventional mode of operation involves the danger of erroneous position estimation—namely exemplarily when the number of radio transmitters of which transmitter identifications recorded before at the reference position are identical to transmitter identifications provided at the position is small and thus an also small RSSI value deviation is determined, which may result in matching which is erroneously estimated as being good. Due to (short-term) shielding effects, it is, for example, possible for not all the radio transmitters to be receivable everywhere. If a reference packet contains radio transmitters A, B and C, a current measurement packet the radio transmitters D, E, the result for the distance will be an (optimum) value 0. The reference packet seems to fit perfectly, even though not a single radio transmitter between the reference and current measurement packets matches.
A modified matching between values or features (such as, for example, transmitter identifications and signal strength values) of stationary radio transmitters currently provided or measured at a current (geographical) position and reference values or features recorded before at a considered (geographical) reference position can be obtained by a kind of filtering of the currently measured features of the radio signals at the position and the reference values of the radio signals recorded before at the reference position. The radio signals here are divided into a first number Neq of radio transmitters of which transmitter identifications recorded before at the reference position are identical to transmitter identifications provided at the current position, and into a second number Nneq of radio transmitters of which transmitter identifications recorded before at the reference position and transmitter identifications provided at the position are different, i.e. the transmitter identifications of which are either provided only at the current position and were not recorded before at the reference position, or the transmitter identifications of which were recorded before only at the reference position and not provided at the current position.
Determining the distance or the measure of correspondence for the position is performed on the basis of the features provided of the radio signals, wherein both features of the first number Neq of radio transmitters and features of the second number Nneq of radio transmitters are taken into account when determining the measure of correspondence, and wherein the features of the first numbers Neq of radio transmitters and the features of the second number Nneq of radio transmitters enter the measure of correspondence differently. With the first number Neq of radio transmitters, transmitter identifications recorded before at the reference position are identical to transmitter identifications provided at the current position. With the second number Nneq of radio transmitters, transmitter identifications are either provided only at the current position and were not recorded before at the reference position, or transmitter identifications were recorded before only at the reference position and are not provided at the current position.
Differences between the electromagnetic features recorded before at the reference positions and the electromagnetic features provided at the current position of the first number Neq of radio transmitters are formed correspondingly. These difference RSSI values ΔRSSI1 to ΔRSSINeq are summed up to form a sum ΣΔRSSIn in accordance with equation (1). After summing up, this sum ΣΔRSSIn is weighted by a weighting factor EQW, i.e. EQW ΣΔRSSIn. EQW here defines a weight between 0 and 1, indicating how strongly the distance of the measuring values or the distance of the signal strength values ΣΔRSSIn is to be weighted compared to the radio transmitters heard in excess or too little at the current position.
If calculating the measure of correspondence was stopped at this stage, it would be possible for reference positions fitting the current position poorer in reality to be selected as candidates instead of better-fitting ones. An example: assuming Neq=1 results for a first reference point when compared to the current position, this means that only one radio transmitter identification between the reference measurement packet and the current measurement packet matches. If the corresponding RSSI values of the corresponding measurement packets are exemplarily randomly apart by 2.5 dB, the result will be ΣΔRSSI1/Neq=2.5 dB. Further assuming Neq=3 results for a second reference point when compared to the current position, this means that three radio transmitter identifications between the reference measurement packet and the current measurement packet match. If the corresponding RSSI values are exemplarily apart from one another by 2 dB, 3 dB and 4 dB, the overall result will be ΣΔRSSIN/Neq=3 dB. The consequence would be that the second reference point would be rated to be poorer than the first one, which would result in an estimate error. Such estimate errors can be avoided or at least reduced using the following modified matching.
For every station present in the reference values, but not in the current measurement values, a penalty value Mnh,m( ) (m=1, . . . , Nnh) may be defined. It may exemplarily be dependent on how reliably the station correspondingly received too little could be received at the reference position in the past. A high penalty value will result, for example, with a previous good receivability of the station received too little, i.e. high RSSI value. Furthermore, the penalty function Mnh,m( ) (m=1, . . . , Nnh) may be combined with a PGS value of the corresponding radio transmitter received too little. A small PGS value in the reference database may exemplarily also result in only a small value of the corresponding penalty function Mnh,m( ). The Nnh penalty values Mnh,m( ) (m=1, . . . , Nnh) for the radio transmitters received too little at the current position are summed up to determine a first sum ΣMnh,m( ) of the Nnh penalty values of the radio transmitters received too little.
In addition, a penalty function Mhtm,r( ) (r=1, . . . , Nhtm) or penalty value may be associated with each radio transmitter received in excess at the current position. Here, too, the function for the penalty value Mhtm,r( ) (r=1, . . . , Nhtm) may be dependent on the current RSSI measurement value of the radio transmitter, and on models, such as, for example, for the environment, the measurement value quality, the age of the reference data, etc. Additionally, the penalty function Mhtm,r( ) (r=1, . . . , Nhtm) may be combined with a PGS value of the corresponding radio transmitter received in excess. A small PGS value in the reference database may exemplarily also result in only a small value of the corresponding penalty function Mhtm,r( ) (r=1, . . . , Nhtm).
The first sum ΣMnh,m( ) of the penalty values of the radio transmitters received too little and the second sum ΣMhtm,r( ) of the radio transmitters received in excess are summed up and weighted by a weighting factor (1−EQW), i.e. (1−EQW) (ΣMnh,m( )+ΣMhtm,r( )).
Finally, the weighted sum EQW ΣΔRSSIn of the differences between electromagnetic features recorded before at the reference position and the electromagnetic features provided at the position of the first number Neq of radio transmitters and the weighted sum (1−EQW) (ΣMnh,m( )+ΣMhtm,r( )) of the penalty values are summed up and normalized using (Neq+Nnh+Nhtm) to obtain the distance value acc between the current position and the considered reference position. The distance value acc exemplarily is calculated according to:
                    acc        =                                                            EQW                ·                                                      ∑                                          n                      =                      1                                        Neq                                    ⁢                                                                          ⁢                                      Δ                    ⁢                                                                                  ⁢                                                                  RSSI                        n                                            ⁡                                              (                                                                                                  )                                                                                                        +                                                (                                      1                    -                    EQW                                    )                                ·                                  (                                                                                    ∑                                                  m                          =                          1                                                                          N                          nh                                                                    ⁢                                                                                          ⁢                                                                        M                                                      nh                            ,                            m                                                                          ⁡                                                  (                                                                                                          )                                                                                      +                                                                  ∑                                                  r                          =                          1                                                                          N                          HTM                                                                    ⁢                                                                                          ⁢                                                                        M                                                      htm                            ,                            r                                                                          ⁡                                                  (                                                                                                          )                                                                                                      )                                                                    (                                                N                  eq                                +                                  N                  nh                                +                                  N                  htm                                            )                                .                                    (        2        )            
If the distance value acc is determined according to equation (2), correspondence between the current position and the considered reference position will be the greater, the smaller the distance value acc. This means that correspondence will be the greater, the smaller the sum ΣΔRSSIn of the differences and the smaller the sums ΣMnh,m( )+ΣMhtm,r( ) of the penalty values. The distance value acc corresponds to the measure of correspondence.
In an urban environment which is characterized by continuous environmental changes, the following problem results when using such a trained method. The database including reference values or reference data are detected at the beginning and may be updated later on continuously or repeatedly. Otherwise, the significance of the reference data decreases—they “age”—and the quality of localization will deteriorate since the receive conditions and/or environmental conditions (recordable environmental information) change over time.
While the fingerprinting method itself does work, the central problem is updating the reference data. Partly, methods in which all the uses are able to rectify gaps and errors in the database by means of “post-training” were suggested in order to keep the cost for setting up and maintaining the database or reference data limited. What is problematic with this approach is the exchange and trustworthiness of such data collected. In order to keep the system operable, erroneous faulty measurements (such as, for example, when a user indicates a wrong actual position when post-training) and deliberate sabotage trials may be prevented from making the common database unusable in any case. Existing approaches for WLAN localization designed for being used in open environments (such as, for example, Place Lab or Skyhook-Wireless) use triangulation instead of fingerprinting as a basic method, including the disadvantages described before. Consequently, these methods need a database in which associating is done from location information of the base station to the base station identification thereof (exemplarily using the MAC address of the base station or access points). Distances to several base stations are estimated from current measurement values and a position is calculated therefrom. In these systems, a secured, reliable database is also set up.
The problem of trustworthiness of trained information and modeling dynamic changes of the environment have only been solved insufficiently. Place Labs converts and imports existing databases including base stations locations from, for example, hot spot operators or from the war-driving-community. Driving up and down streets with the aim of tracking down WLAN stations and providing same with a location reference is referred to as war-driving. War-drivers here use a WLAN-enabled laptop which is additionally equipped with a GPS receiver. The problem here is that topicality of the data, in particular with regard to private stations, cannot be guaranteed. Precision and trustworthiness of these methods are both doubtful.
Skyhook Wireless tries to solve the problem by the cooperation with so-called “scanners”. They are specially selected trusted users who maintain the database by targeted war-driving. This means that keeping the database in a current state entails high cost, quick adaptation is not possible when changing access points. Skyhook Wireless at present offer their customers an annual update of the database. In order for the database nevertheless not to age too quickly, access points which do not belong to public hot spots of big providers (which are thus potentially continuously in operation and stationary at one location) are excluded from the system. However, this results in a considerable decrease in area coverage, since a majority of WLAN base stations installed are already of private, non-public nature (SOHO, industry, etc.) and thus mostly evade control and information provision.
The methods described before which are partly used already can only update the database in great time intervals. Consequently, they do not offer practical handling or a practical concept of handling of stations active only at times.
This problem is of particular relevance for private stations which represent a strongly increasing part of the stations, since such private stations are frequently operated only when needed, due to objections with regard to the danger of breaking in the WLAN network or due to radiation exposure. The solutions implemented so far, in particular, do not allow to perform localization of terminal devices reliably without using external positioning systems in urban regions of interest in which, on the one hand, receive conditions are too difficult for triangulation and, on the other hand, the base stations or communication partners available change frequently.
WO 2008/113439 A1 discloses an apparatus and a method for localizing terminal devices. Environmental information are determined here using a terminal device. Then, the position of the terminal device is determined on the basis of the environmental information. Subsequently, environmental information deviating from reference environmental information associated with the position of the terminal device is ascertained so as to be able to finally take an updating measure when a deviation is found. In order to keep the reference data or reference environmental information used by the mobile terminal device in a current and uncorrupted state, the deviations determined of the environmental information from the reference environmental information have to be evaluated with regard to their relevance and trustworthiness. For this purpose, an evaluating means which is based on two criteria is provided. The observation and/or deviation has to contain a minimum measure of change compared to the current state of the reference data. In addition, the observation should be reproducible. Additionally, further criteria which influence the relevance of the observation may be defined. Examples of a minimum measure of a deviation observed or a change are the number of base stations seen, added or dropped, and the variation of the receive field strength of individual stations. An example of the reproducibility criterion may be that the same observation or the same deviation has to be observed several times by the respective mobile terminal device before it may be used for updating the reference data. Alternatively, a similar observation or a similar deviation may have to be made by several independent sources.